package zd.vrp.ga;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

import zd.vrp.utils.SolutionComparator;
import zd.vrp.utils.SortObject;
import zd.vrp.utils.TestUtils;

public class GA {

	//population size
	public int populationSize = 20;
	
	//population
	public List<List> polulation = new ArrayList<List>();
	
	
	private List<SortObject> soList = new ArrayList<SortObject>();
	
	//fitness value
	private double[] fitness;
	//total fitness value
	private double totalFitness = 0;
	
	//first parent
	private List firstParent;
	//second parent
	private List secondParent;
	
	//these two variables are used to calculate fitness value
	public double MAX = 1.6;
	public double MIN = 0.4;

	public int getPopulationSize() {
		return populationSize;
	}

	public void setPopulationSize(int populationSize) {
		this.populationSize = populationSize;
	}

	public List<List> getPolulation() {
		return polulation;
	}

	public void setPolulation(List<List> polulation) {
		this.polulation = polulation;
	}
	
	//generate initial solution
	public void getInitPopulation(){
		InitialSolution is = new InitialSolution();
		for(int i=0;i<this.populationSize;i++){
			this.polulation.add(is.randGenePop());
		}		
	}
	
	//calculate rank for each solution
	public void calFitness(){
		soList.clear();
		totalFitness = 0.0;
		
		//sort all the solution according to vehicle number and tour length
		for(int i=0;i<this.populationSize;i++){
			int vehicleNum = this.polulation.get(i).size();
			double tourLength = TestUtils.getTotalLength(this.polulation.get(i));
			SortObject so = new SortObject();
			so.setPosition(i);
			so.setValue(vehicleNum);
			so.setValue2(tourLength);
			soList.add(so);
		}
		
		Collections.sort(soList,new SolutionComparator());
		
		//calculate fitness value
		fitness = new double[this.populationSize];
		int p = soList.size();
		for(int i=0;i<p;i++){
			double f = this.MAX - (this.MAX-this.MIN)*i/(p-1);			
			fitness[i] = f;
			totalFitness += f;
		}
	}
	
	//randomly choose two parent according to fitness value
	public void chooseParents(double[] fitness){
	
		//randomly universal selection
		double startRand = Math.random()*totalFitness/populationSize;
		System.out.println("start random:"+startRand);
		System.out.println("total fitness:"+totalFitness);
		
		double tempTotalFitness = 0;
		double tempTotalFitnessF = 0;
		double[] tempTotalFitnessArray = new double[populationSize];
		int i=1;
		List<Integer> tempIndex = new LinkedList<Integer>();
		double susTotal = 0;
		int j=0;
		
		tempTotalFitnessArray[0] = fitness[0];
		
		for(j=1;j<populationSize;j++){
			tempTotalFitnessArray[j] = tempTotalFitnessArray[j-1] + fitness[j];
		}
		
		while(i*startRand<totalFitness){
			for(int ij=0;ij<tempTotalFitnessArray.length;ij++){
				if(tempTotalFitnessArray[ij]>i*startRand){
					
				}
			}
			i++;
		}
		
	/*	while(i*startRand < totalFitness){
			
			for(int jj=j;jj<populationSize-1;jj++){
				if(jj==0){
					tempTotalFitness = 0;
				}else{
					tempTotalFitness += fitness[jj-1];
				}
	
				tempTotalFitnessF = tempTotalFitness + fitness[jj];
				
				if(tempTotalFitness<=i*startRand && tempTotalFitnessF > i*startRand){
					System.out.println("********************");
					tempIndex.add(jj);
					i++;
					j = jj;
					susTotal += fitness[jj];
					jj++;
					break;
				}
			}
			
		}*/
		
		
		
		System.out.print("[");
		for(int l=0;l<tempIndex.size();l++){
			System.out.print(tempIndex.get(l)+"  ");
		}
		System.out.println("]");
		
		//roulette wheel selection
		double firstRand = Math.random()*susTotal;
		double tempT1 = 0.0;
		for(int k=0;k<tempIndex.size();k++){
			tempT1 += fitness[tempIndex.get(k)];
			if(tempT1 >= firstRand){
				
				firstParent = polulation.get(soList.get(tempIndex.get(k)).getPosition());
				susTotal = susTotal - fitness[tempIndex.get(k)];
				System.out.println("first parent:" + fitness[tempIndex.get(k)]);
				
				
				tempIndex.remove(k);
				
				break;
			}
		}
		double secondRand = Math.random()*susTotal;
		double tempT2 = 0.0;
		for(int k=0;k<tempIndex.size();k++){
			tempT2 += fitness[tempIndex.get(k)];
			if(tempT2 >= secondRand){
				secondParent = polulation.get(soList.get(tempIndex.get(k)).getPosition());
				System.out.println("second parent:"+fitness[tempIndex.get(k)]);
				break;
			}
		}
	}
	
	/*****************************/
	//total ga procedures
	public GA(){
		//1. initial population
		getInitPopulation();
		
		//2.1 calcualte fitness value for each solution
		calFitness();
		System.out.print("[");
		for(int i=0;i<fitness.length;i++){
			System.out.print(fitness[i]+"  ");
		}
		System.out.println("]");
		//2.2 choose two parents
		chooseParents(fitness);
		
	}
	/*****************************/

	public List<SortObject> getSoList() {
		return soList;
	}

	public void setSoList(List<SortObject> soList) {
		this.soList = soList;
	}
	
	
}
